class DataOut
{
	int left;
	int right;
	int sum;
	DataOut(int a, int b, int c)
	{
		left = a;
		right = b;
		sum = c;
	}
}
public class FindMaxSubarray 
{
	public static DataOut findMaxCrossingSubarray(int[] A, int low, int mid, int high)
	{
		int leftSum = -1000;
		int rightSum = -1000;
		int maxLeft = 0;
		int maxRight = 0;
		int sum = 0;
		for (int i=mid; i >= low; --i) 
		{
			sum += A[i];
			if (sum > leftSum) 
			{
				leftSum = sum;
				maxLeft = i;
			}
		}
		sum = 0;
		for (int i=mid+1; i <= high; ++i) 
		{
			sum += A[i];
			if (sum > rightSum) 
			{
				rightSum = sum;
				maxRight = i;
			}
		}
		return new DataOut(maxLeft, maxRight, leftSum + rightSum);
	}

	public static DataOut findMaxSusbarray(int[] A, int low, int high)
	{
		DataOut left;
		DataOut right;
		DataOut cross;
		if (low == high) 
			return new DataOut(low, high, A[low]);
		else
		{
			int mid = (low+high) / 2;
			left = findMaxSusbarray(A, low, mid);
			right = findMaxSusbarray(A, mid+1, high);
			cross = findMaxCrossingSubarray(A, low, mid, high);
			if (left.sum >= right.sum && left.sum >= cross.sum) 
				return left;	
			else if (right.sum >= left.sum && right.sum >= cross.sum) 
				return right;	
			else
				return cross;
		}
	}
	
	public static void main(String[] args)
	{
		int[] A = {0, 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
		DataOut dout = findMaxSusbarray(A, 1, 16);
		System.out.println(dout.left + "\n" + dout.right + "\n" + dout.sum);
	}
}
